Telecommunications channels often carry traffic that is multiplexed from several sources. For example, a 2.488 Gb/s SONET STS-48 channel carries 48 51.84 Mb/s SONET STS-1 channels that are time multiplexed on a byte-by-byte basis. That is, the channel carries bytes 1.1, 2.1, 3.1, . . . , 48.1, 1.2, 2.2, 3.2, . . . , 48.2, 1.3, 2.3, 2.3, . . . where n.m denotes byte m of subchannel n. Details of the SONET format can be found in Ming-Chwan Chow, Understanding SONET/SDH: Standards & Applications, Andan Pub, ISBN 0965044823, 1995 and in ANSI Standard T1.105-1995.
An STS-1 SONET frame is a repeating structure of 810 bytes arranged into 9 rows of 90 columns. The frame structure is transmitted in row-major order. That is, all 90-bytes of row 0 are transmitted, then all 90 bytes of row 1, and so on. At higher multiplexing rates, each byte of the STS-1 frame is replaced by a number of bytes, one from each of several multiplexed sources. For example, at STS-48, 48 bytes, one from each of 48 STS-1 subframes, are transmitted during each column interval. In this case, the order of transmission is to send all 48 subframe bytes for one column before moving on to the next column and to send all of the columns of a row before moving on to the next row.
A digital cross connect is a network element that accepts a number of multiplexed data channels, for example 72 STS-48 channels, and generates a number of multiplexed output channels where each output channel carries an arbitrary set of the subchannels from across all of the input ports. For example, one of the STS-48 output channels may contain STS-1 channels from different input channels in a different order than they were originally input.
An example of digital cross connect operation is shown in FIG. 1. The figure shows a cross connect 30 with two input ports and two output ports. Each of these ports contains four time slots. Input port 1 (the top input port) carries subchannels A, B, C, and D in its four slots and input port 2 (the bottom port) carries subchannels E, F, G, and H in its four time slots. Each time slot of each output port can select any time slot of any input port. For example, output port 1 (top) carries subchannels H, D, F, and A from 2.4, 1.4, 2.2, 1.1 where x.y denotes input port x, timeslot y. Input timeslots are typically switched in both space and time. The first time slot of output port 1, for example, is switched in time from slot 4 to slot 1 and in space from port 2 to port 1. Also, some time slots may be duplicated (i.e., multicast) and others dropped. Subchannel A, for example, appears in output time slots 1.4 and 2.2 and subchannel G is dropped, appearing on no output time slot.
A digital cross connect can be implemented in a straightforward manner by demultiplexing each input port, switching all of the time slots of all of the input ports with a space switch, and then multiplexing each output port. This approach is illustrated in FIG. 2. The four time slots of input port 1 are demultiplexed in demultiplexers 32 so that each is carried on a separate line. All of these demultiplexed lines are then switched by a space switch 34 to the appropriate output time slots. Finally, a set of multiplexers 36 multiplexes the time slots of each output channel onto each output port. This approach is used, for example, in the systems described in U.S. Pat. Nos. 3,735,049 and 4,967,405.
The space-switch architecture for a digital cross connect as shown in FIG. 2 has the advantage that it is conceptually simple and strictly non-blocking for any type of traffic, including unicast and multicast traffic. A switch architecture is strictly non-blocking if an existing configuration can be augmented to handle any new connection between an idle input time slot and an idle output time slot without changing the time slots assigned to any existing connection. However, this space-switch architecture results in switches that are too large to be economically used for large cross connects. For example, a digital cross connect with P=72 ports and T=48 time slots requires a PT×PT (3456×3456) space switch with P2T2=11,943,936 cross points. Further, this large switch will be operated at a very slow rate. It will only need to switch a new batch of input time slots after T bytes have been received. Thus, it operates at a 1/T byte rate.
A more economical digital cross connect can be realized using a time-space-time (T-S-T) switch architecture as illustrated in FIG. 3. Here each input port is input to a time-slot interchanger (TSI) 38a, 38b. A TSI switches a multiplexed input stream in time by interchanging the positions of the time slots. To switch time-slot i to time-slot j, for example, slot i is delayed by T+j−i byte times. The multiplexed streams out of the input TSIs are then switched by a P x P space switch 40 that is reconfigured on each time slot. The outputs of this space switch are switched in time again by a set of output TSIs 42a, 42b. This T-S-T architecture is employed, for example, by the systems described in U.S. Pat. Nos. 3,736,381 and 3,927,267.
An example of the operation of a T-S-T digital cross connect on the configuration of FIG. 3 is shown in FIG. 4. Here the TSI 38a for input port 1 does not change the positions of its input time slots. The input TSI 38b for port 2, however, reorders its time slots from E, F, G, H, to -, F, H, E. The G here is dropped as it is not used by any output ports. The space switch 40 takes the outputs of the two input TSIs 38a, 38b and switches them, without changing time slots, to create the streams A, F, H, D and A, B, C, E. Note that this involves a dualcast of timeslot A to both outputs. Finally, the output TSIs 42a, 42b reorder these streams to give the output streams H, D, F, A and E, A, B, C.
A three-stage T-S-T digital cross connect is logically equivalent to a 3-stage Clos network with P T×T input stages, T P×P center stages, and P T×T output stages. For example, FIG. 5 shows the configuration of FIG. 4 on an equivalent 3-stage S-S-S (space-space-space) Clos network. To route a configuration of input time slots to output time slots on a Clos switch network switch, a center stage time slot must be assigned to each connection. This routing in a Clos network is described in detail in Clos, Charles, “A Study of Non-Blocking Switching Networks,” Bell System Technical Journal, March 1953, pp. 406-424, and V. E. Benes, “On Rearrangeable Three-Stage Connecting Networks,” The Bell System Technical Journal, vol. XLI, No. 5, September 1962, pp. 1481-1492. These references show that a three-stage Clos network is rearrangeably non-blocking for unicast traffic but cannot, in general route multicast traffic. A network is rearrangeably non-blocking, or rearrangeable, if for every input to output connection, there exists an assignment of center stage time slots that will route that connection.
In the past this scheduling problem was solved using a looping algorithm that is described in Benes, The Mathematical Theory of Connecting Networks, 1964. There have been many minor variations to this basic scheduling algorithm. U.S. Pat. No. 3,576,398 describes a scheduling algorithm that prioritizes the scheduling of certain connections over others. U.S. Pat. No. 4,004,103 describes a scheduling algorithm that randomizes the allocation of paths. U.S. Pat. No. 5,345,441 allocates different sized contiguous blocks of calls. U.S. Pat. No. 5,430,716 describes a method for scheduling multicast and broadcast calls. U.S. Pat. No. 5,987,027 describes a rearrangement algorithm for scheduling multicast calls. U.S. Pat. No. 6,034,947 describes the use of scheduling for protection switching. U.S. Pat. No. 5,408,231 describes another alternative implementation.